/* 
 * First Missing Positive
 * For example, Given[1,2,0] return 3
 * Given[3,4,-1,1] return 2;
 */

#include "../func.h"

int firstMissingPositive(vector<int> &nums)
{
    bucket_sort(nums);

    for (int i = 0; i < nums.size(); ++i)
    {
        if (nums[i] != (i + 1))
            return i + 1;
    }
    return nums.size() + 1;
}

void bucket_sort(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; ++i)
    {
        while (A[i] != i + 1)
        {
            if (A[i] <= 0 || A[i] > n || A[i] == A[A[i] - 1])
                break;
            swap(A[i], A[A[i] - 1]);
        }
    }
}